package _dp

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/climbing-stairs/description/
https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html

70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
 */
class leetcode_70 {
    @Test
    fun test_1() {
        val actual = climbStairs(2)
        val expect = 2
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val actual = climbStairs(3)
        val expect = 3
        Assert.assertEquals(expect, actual)
    }

    fun climbStairs(n: Int): Int {
        return climbStairs1(n)
        // return climbStairs2(n)
    }

    private fun climbStairs1(n: Int): Int {
        // 动态规划
        // T - N
        // S - 1

        if(n == 1){
            return 1
        }
        if(n == 2){
            return 2
        }
        // 1 确定数组以及下标含义
        val dp: IntArray=IntArray(n+1)
        // 2 确定递推公式： f(i) = f(i-1) + f(i-2)
        // 3 初始化数组
        dp[1] = 1
        dp[2] = 2
        // 4 遍历顺序
        for(i in 3 .. n){
            dp[i] = dp[i-1] + dp[i-2]
            // 5 打印数组
            println("dp[$i] = dp[${i-1}] + dp[${i-2}] =  ${dp[i-1]} + ${dp[i-2]}=${dp[i]}")
        }
        return dp[n]
    }

    private fun climbStairs2(n: Int): Int {
        // 递归 - 超时
        if (n == 1) {
            return 1
        }
        if (n == 2) {
            return 2
        }

        val result: Int = climbStairs2(n - 1) + climbStairs2(n - 2)
        println("n - ${result}")
        return result
    }
}